package newcoder_exp.justPractise;
import java.util.*;


public class Ex37 {
    public class Interval {
        int start;
        int end;
        Interval() { start = 0; end = 0; }
        Interval(int s, int e) { start = s; end = e; }
    }

    public class Solution {
        public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
            int len;
            if (intervals == null || (len = intervals.size()) == 0)
                return new ArrayList<>();
            Deque<Interval> deque = new LinkedList<>();
            Queue<Interval> queue = new PriorityQueue<Interval>((i1, i2) -> i1.start - i2.start);
            for (int i = 0; i < len; i++) {
                queue.offer(intervals.get(i));
            }
            deque.offerLast(queue.poll());
            Interval last, cur;
            while (!queue.isEmpty()) {
                last = deque.peekLast();
                cur = queue.poll();
                if (last.end > cur.start) {
                    last = deque.pollLast();
                    if (last.end > cur.end) {
                        deque.offerLast(last);
                    } else {
                        deque.offerLast(new Interval(last.start, cur.end));
                    }
                } else {
                    deque.offerLast(cur);
                }
            }
            return new ArrayList<>(deque);
        }
    }
}
